import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author VernHe
 * @date 2021年05月09日 15:15
 */
public class Solution_023 {
    public static void main(String[] args) {
        ListNode[] listNodes = new ListNode[3];
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(4);
        node1.next.next = new ListNode(5);

        ListNode node2 = new ListNode(1);
        node2.next = new ListNode(3);
        node2.next.next = new ListNode(4);

        ListNode node3 = new ListNode(2);
        node3.next = new ListNode(6);

        listNodes[0] = node1;
        listNodes[1] = node2;
        listNodes[2] = node3;
        ListNode node = new Solution_023().mergeKLists(listNodes);
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = new ListNode();
        PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((ListNode)o1).val - ((ListNode)o2).val;
            }
        });
        for (ListNode list : lists) {
            if (list != null) {
                queue.add(list);
            }
        }

        ListNode node = res;
        ListNode cur = null;
        while (!queue.isEmpty()) {
            // 每次选择一个最小的
            cur = queue.poll();
            node.next = cur;
            node = node.next;
            // 把它的下一个加入到队列中
            if (cur.next != null) {
                queue.add(cur.next);
            }
        }

        res = res.next;
        return res;
    }


}
